{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Subtree with all the Deepest Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subtreeWithAllDeepest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #具有所有最深节点的最小子树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个根为&nbsp;<code>root</code>&nbsp;的二叉树，每个节点的深度是 <strong>该节点到根的最短距离</strong> 。</p>\n",
    "\n",
    "<p>返回包含原始树中所有 <strong>最深节点</strong> 的 <em>最小子树</em> 。</p>\n",
    "\n",
    "<p>如果一个节点在 <strong>整个树 </strong>的任意节点之间具有最大的深度，则该节点是 <strong>最深的</strong> 。</p>\n",
    "\n",
    "<p>一个节点的 <strong>子树</strong> 是该节点加上它的所有后代的集合。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/01/sketch1.png\" style=\"width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,5,1,6,2,0,8,null,null,7,4]\n",
    "<strong>输出：</strong>[2,7,4]\n",
    "<strong>解释：</strong>\n",
    "我们返回值为 2 的节点，在图中用黄色标记。\n",
    "在图中用蓝色标记的是树的最深的节点。\n",
    "注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "<strong>解释：</strong>根节点是树中最深的节点。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,1,3,null,2]\n",
    "<strong>输出：</strong>[2]\n",
    "<strong>解释：</strong>树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数量在<meta charset=\"UTF-8\" />&nbsp;<code>[1, 500]</code>&nbsp;范围内。</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 500</code></li>\n",
    "\t<li>每个节点的值都是 <strong>独一无二</strong> 的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与力扣 1123 重复：<a href=\"https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/\" target=\"_blank\">https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-subtree-with-all-the-deepest-nodes](https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-subtree-with-all-the-deepest-nodes](https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,1,6,2,0,8,null,null,7,4]', '[1]', '[0,1,3,null,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return root\n",
    "        level = [root]\n",
    "        depth = 0\n",
    "        while(1):\n",
    "            depth+=1\n",
    "            level_next = []\n",
    "            for node in level:\n",
    "                if node.left: level_next.append(node.left)\n",
    "                if node.right: level_next.append(node.right)\n",
    "            if not level_next:\n",
    "                break\n",
    "            level=level_next\n",
    "            \n",
    "        last_level = set(level)\n",
    "        max_h =0\n",
    "        \n",
    "        # for node in last_level:\n",
    "        #     print(node.val)\n",
    "        ans = None\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return False,0\n",
    "                \n",
    "            l_has, l_h = dfs(root.left)\n",
    "            r_has, r_h = dfs(root.right)\n",
    "            has = l_has or r_has or root in last_level\n",
    "            good = l_has and r_has or root in last_level \n",
    "            h = max(l_h,r_h)+1\n",
    "            if h > max_h and good:\n",
    "                ans = root\n",
    "            return has,h\n",
    "        dfs(root)\n",
    "        return ans \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return node, 0\n",
    "            l, lh = dfs(node.left)\n",
    "            r, rh = dfs(node.right)\n",
    "            if lh > rh:\n",
    "                return l, lh + 1\n",
    "            elif lh < rh:\n",
    "                return r, rh + 1\n",
    "            else:\n",
    "                return node, lh + 1\n",
    "        return dfs(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        depth = {None: -1}\n",
    "        def dfs(node, level = 0):\n",
    "            if not node:\n",
    "                return\n",
    "            level += 1\n",
    "            depth[node] = level\n",
    "            dfs(node.left, level)\n",
    "            dfs(node.right, level)\n",
    "        dfs(root)\n",
    "\n",
    "        max_depth = max(depth.values())\n",
    "\n",
    "        def ans(node):\n",
    "            if not node or depth.get(node) == max_depth:\n",
    "                return node\n",
    "            left, right = ans(node.left), ans(node.right)\n",
    "            return node if left and right else left or right\n",
    "\n",
    "        return ans(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def dfs(root, parent, d, depth):\n",
    "    if not root:\n",
    "        return\n",
    "\n",
    "    root.depth = depth\n",
    "    root.parent = parent\n",
    "    if d[\"maxDepth\"] == depth:\n",
    "        d[\"result\"].append(root)\n",
    "    elif d[\"maxDepth\"] < depth:\n",
    "        d[\"maxDepth\"] = depth\n",
    "        d[\"result\"] = [root]\n",
    "    dfs(root.left, root, d, depth + 1)\n",
    "    dfs(root.right, root, d, depth + 1)\n",
    "\n",
    "def isAllNodesSame(nodes):\n",
    "    val = nodes[0].val\n",
    "    for node in nodes:\n",
    "        if val != node.val:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        d = { \"maxDepth\": 0, \"result\": [] }\n",
    "        dfs(root, None, d, 0)\n",
    "        nodes = d[\"result\"]\n",
    "        if len(nodes) == 0:\n",
    "            return None\n",
    "        while not isAllNodesSame(nodes):\n",
    "            for i in range(len(nodes)):\n",
    "                nodes[i] = nodes[i].parent\n",
    "\n",
    "        return nodes[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        if not root: return root\n",
    "\n",
    "        # 题目说的模糊,其实是求一个最小子树,使得这个子树的根节点可以覆盖所有的最深的节点\n",
    "        def dfs(root):\n",
    "            # 返回一个元素(当前的层数,符合题意的节点)\n",
    "            if not root: return -1, None\n",
    "            d_l, left_node = dfs(root.left)\n",
    "            d_r, right_node = dfs(root.right)\n",
    "            return_node = root if d_l == d_r \\\n",
    "                else (left_node if d_l > d_r else right_node)\n",
    "            return max(d_l, d_r) + 1, return_node\n",
    "\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        # Step 1. 先記錄各node的深度，以及最大深度\n",
    "        dict_depth = {}\n",
    "        def dfs(node, depth):\n",
    "            if node == None:\n",
    "                return\n",
    "            dict_depth[node] = depth\n",
    "            dfs(node.left, depth + 1)\n",
    "            dfs(node.right, depth + 1)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        max_depth = 0\n",
    "        for value in dict_depth.values():\n",
    "            if value > max_depth:\n",
    "                max_depth = value\n",
    "        print(max_depth)\n",
    "        \n",
    "        # Step 2. 取出包含所有最深節點的父節點\n",
    "        def dfs2(node):\n",
    "            if node == None:\n",
    "                return None\n",
    "\n",
    "            left_node = dfs2(node.left)\n",
    "            right_node = dfs2(node.right)\n",
    "            if (left_node != None) and (right_node != None):\n",
    "                return node\n",
    "            elif left_node != None:\n",
    "                return left_node\n",
    "            elif right_node != None:\n",
    "                return right_node \n",
    "            elif dict_depth[node] == max_depth:\n",
    "                return node\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        return dfs2(root)\n",
    "\n",
    "        # # Tag each node with it's depth.\n",
    "        # depth = {None: -1}\n",
    "        # def dfs(node, parent = None):\n",
    "        #     if node:\n",
    "        #         depth[node] = depth[parent] + 1\n",
    "        #         dfs(node.left, node)\n",
    "        #         dfs(node.right, node)\n",
    "        # dfs(root)\n",
    "\n",
    "        # max_depth = max(depth.itervalues())\n",
    "\n",
    "        # def answer(node):\n",
    "        #     # Return the answer for the subtree at node.\n",
    "        #     if not node or depth.get(node, None) == max_depth:\n",
    "        #         return node\n",
    "        #     L, R = answer(node.left), answer(node.right)\n",
    "        #     return node if L and R else L or R\n",
    "\n",
    "        # return answer(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        queue=[(root,None,0)]\n",
    "        res=[]\n",
    "        hashmap={}\n",
    "        while queue:\n",
    "            node,p,level=queue.pop(0)\n",
    "            if len(res)==level:\n",
    "                res.append([])\n",
    "            res[level].append(node)\n",
    "            hashmap[node]=p\n",
    "            if node.left:\n",
    "                queue.append((node.left,node,level+1))\n",
    "            if node.right:\n",
    "                queue.append((node.right,node,level+1))\n",
    "        #print(res[-1])\n",
    "        #print(hashmap)\n",
    "        if len(res[-1])==1:\n",
    "            return res[-1][0]\n",
    "        setA=set(res[-1])\n",
    "        #print(setA)\n",
    "        #setB=set()\n",
    "\n",
    "       \n",
    "        while len(setA)>1:\n",
    "            setB=set()\n",
    "            for k in setA:\n",
    "                setB.add(hashmap[k])\n",
    "            setA=setB\n",
    "            print(setA)\n",
    "\n",
    "            \n",
    "        #print(setB)\n",
    "        return setB.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    ans = None\n",
    "    s = []\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        queue = [root]\n",
    "        newqueue = []\n",
    "        tmp = []\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node:\n",
    "                tmp.append(node)\n",
    "                if node.left:\n",
    "                    newqueue.append(node.left)\n",
    "                if node.right:\n",
    "                    newqueue.append(node.right)\n",
    "            if not queue:\n",
    "                if not newqueue:\n",
    "                    break\n",
    "                queue = newqueue                \n",
    "                tmp = []\n",
    "                newqueue = []\n",
    "        if len(tmp) == 1:\n",
    "            return tmp[0]\n",
    "        self.s = tmp\n",
    "        def f(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if root in self.s:\n",
    "                return 1\n",
    "            l = f(root.left)\n",
    "            r = f(root.right)\n",
    "            if l + r == len(self.s) and not (l==0 or r==0):\n",
    "                self.ans = root\n",
    "            return l+r\n",
    "        f(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        left = self.height(root.left)\n",
    "        right = self.height(root.right)\n",
    "        if left == right:\n",
    "            return root\n",
    "        elif left > right:\n",
    "            return self.subtreeWithAllDeepest(root.left)\n",
    "        else:\n",
    "            return self.subtreeWithAllDeepest(root.right)\n",
    "\n",
    "\n",
    "    def height(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.height(root.left), self.height(root.right))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        # depth_dict = {None: -1}\n",
    "\n",
    "        # def helper(node, parent=None):\n",
    "        #     if not node:\n",
    "        #         return None\n",
    "\n",
    "        #     depth_dict[node] = depth_dict[parent] + 1\n",
    "        #     helper(node.left, node)\n",
    "        #     helper(node.right, node)\n",
    "\n",
    "        # helper(root)\n",
    "        # # print(depth_dict)\n",
    "        # max_depth = max(depth_dict.values())\n",
    "        # print(max_depth)\n",
    "\n",
    "        # def answer(node):\n",
    "        #     if not node or depth_dict.get(node, None) == max_depth:\n",
    "        #         return node\n",
    "\n",
    "        #     left = answer(node.left)\n",
    "        #     right = answer(node.right)\n",
    "\n",
    "        #     if left and right:\n",
    "        #         return node\n",
    "\n",
    "        #     if left:\n",
    "        #         return left\n",
    "\n",
    "        #     if right:\n",
    "        #         return right\n",
    "\n",
    "        # return answer(root)\n",
    "\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        def helper_depth(node):\n",
    "            # 二叉树的深度\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            left = helper_depth(node.left)\n",
    "            right = helper_depth(node.right)\n",
    "\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        left_depth = helper_depth(root.left)\n",
    "        right_depth = helper_depth(root.right)\n",
    "\n",
    "        if left_depth > right_depth:\n",
    "            return self.subtreeWithAllDeepest(root.left)\n",
    "        elif left_depth < right_depth:\n",
    "            return self.subtreeWithAllDeepest(root.right)\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        # dfs 同时返回最大深度+包含最大深度节点的子树\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return (None, 0)\n",
    "            \n",
    "            left_node, left_dist = dfs(node.left)\n",
    "            right_node, right_dist = dfs(node.right)\n",
    "            if left_dist > right_dist:\n",
    "                return (left_node, left_dist+1)\n",
    "            elif right_dist > left_dist:\n",
    "                return (right_node, right_dist+1)\n",
    "            else:\n",
    "                return (node, left_dist+1)\n",
    "\n",
    "        node, _ = dfs(root)\n",
    "        return node "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root):\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, None\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left[0] > right[0]:\n",
    "                return left[0] + 1, left[1]\n",
    "            elif left[0] < right[0]:\n",
    "                return right[0] + 1, right[1]\n",
    "            else:\n",
    "                return left[0] + 1, node\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root):\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, None\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left[0] > right[0]:\n",
    "                return left[0] + 1, left[1]\n",
    "            elif left[0] < right[0]:\n",
    "                return right[0] + 1, right[1]\n",
    "            else:\n",
    "                return left[0] + 1, node\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                node.par = par\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        rootnodes = []\n",
    "        def traverse(node,depth):\n",
    "            if node.left == None and node.right == None:\n",
    "                rootnodes.append((node,depth))\n",
    "            else:\n",
    "                if node.left:\n",
    "                    traverse(node.left,depth+1)\n",
    "                if node.right:\n",
    "                    traverse(node.right,depth + 1)\n",
    "        traverse(root,0)\n",
    "        maxd = max([i[1] for i in rootnodes])\n",
    "        trueroots = [] \n",
    "        for i in rootnodes:\n",
    "            if i[1] == maxd:\n",
    "                trueroots.append(i[0])\n",
    "        trueroots = set(trueroots)\n",
    "        while len(trueroots) > 1:\n",
    "            newset = set()\n",
    "            for i,node in enumerate(trueroots):\n",
    "                newset.add(node.par)\n",
    "            trueroots = newset\n",
    "        return trueroots.pop()\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        #好像做过，就是左高度如果不等右高度就递归深的\n",
    "        #如果等于就返回当前\n",
    "        if h(root.left)==h(root.right):\n",
    "            return root\n",
    "        if h(root.left)>h(root.right):\n",
    "            return self.subtreeWithAllDeepest(root.left)\n",
    "        else:\n",
    "            return self.subtreeWithAllDeepest(root.right)\n",
    "d={None:0}\n",
    "def h(node):\n",
    "    if node not in d:\n",
    "        d[node]=1+max([h(node.left),h(node.right)]) \n",
    "    return d[node]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(maxsize = None)\n",
    "    def height(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.height(root.left), self.height(root.right)) + 1\n",
    "        \n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        \"\"\"\n",
    "        如果 左子树高度 等于 右子树高度，则为所求答案\n",
    "        如果 左子树高度 大于 右子树高度，则往左子树递归查找\n",
    "        如果 左子树高度 小于 右子树高度，则往右子树递归查找\n",
    "        \"\"\"\n",
    "        left_height, right_height = self.height(root.left), self.height(root.right)\n",
    "        if left_height == right_height:\n",
    "            return root\n",
    "        elif left_height > right_height:\n",
    "            return self.subtreeWithAllDeepest(root.left)\n",
    "        elif left_height < right_height:\n",
    "            return self.subtreeWithAllDeepest(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    paths = []\n",
    "    largest = 0\n",
    "    left_idx = 0\n",
    "    right_idx = 0\n",
    "    def search_most(self, last_node, cur_nodes):\n",
    "        if last_node.left is None and last_node.right is None:\n",
    "            #for n in cur_nodes:\n",
    "            #    print(n.val),\n",
    "            #print(\"\\n\")\n",
    "            import copy\n",
    "            #new_path = copy.deepcopy(cur_nodes)\n",
    "            cur_len = len(cur_nodes)\n",
    "            if cur_len > self.largest:\n",
    "                self.largest = cur_len\n",
    "                self.paths.append(copy.deepcopy(cur_nodes))\n",
    "                self.left_idx = self.right_idx = len(self.paths) - 1\n",
    "            elif cur_len == self.largest:\n",
    "                self.paths.append(copy.deepcopy(cur_nodes))\n",
    "                self.right_idx = len(self.paths) - 1\n",
    "                \n",
    "            return\n",
    "\n",
    "        if last_node.left is not None:\n",
    "            cur_nodes.append(last_node.left)\n",
    "            self.search_most(last_node.left, cur_nodes)\n",
    "            cur_nodes.pop(-1)\n",
    "        if last_node.right is not None:\n",
    "            cur_nodes.append(last_node.right)\n",
    "            self.search_most(last_node.right, cur_nodes)\n",
    "            cur_nodes.pop(-1)\n",
    "\n",
    "        \n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        self.paths = []\n",
    "        self.largest = 0\n",
    "        self.left_idx = 0\n",
    "        self.right_idx = 0\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.left is None and root.right is None:\n",
    "            return root\n",
    "        node_path = [root]\n",
    "        self.search_most(root, node_path)\n",
    "        i = self.left_idx\n",
    "        j = self.right_idx\n",
    "        #print(i)\n",
    "        #print(j)\n",
    "        #print(len(self.paths[i]))\n",
    "\n",
    "        for k in range(self.largest):\n",
    "            if self.paths[i][k].val != self.paths[j][k].val:\n",
    "              #  print(k)\n",
    "                return self.paths[i][k-1]\n",
    "        return self.paths[i][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None, 0\n",
    "            left, i = dfs(root.left)\n",
    "            right, j = dfs(root.right)\n",
    "            if i > j:\n",
    "                return left, i + 1\n",
    "            elif j > i:\n",
    "                return right, j + 1\n",
    "            return root, i + 1\n",
    "        return dfs(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        dp = {None: -1}\n",
    "        def dfs(node, parent = None):\n",
    "            if node:\n",
    "                dp[node] = dp[parent] + 1\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        dfs(root)\n",
    "        mxd = max(dp.values())\n",
    "        # print(mxd)\n",
    "        def res(node):\n",
    "            if not node or dp.get(node, None) == mxd:\n",
    "                return node\n",
    "            l, r = res(node.left), res(node.right)\n",
    "            return node if l and r else l or r\n",
    "        return res(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        Result = collections.namedtuple(\"Result\", (\"node\", \"dist\"))\n",
    "        def dfs(node):\n",
    "            # Return the result of the subtree at this node.\n",
    "            if not node: return Result(None, 0)\n",
    "            L, R = dfs(node.left), dfs(node.right)\n",
    "            if L.dist > R.dist: return Result(L.node, L.dist + 1)\n",
    "            if L.dist < R.dist: return Result(R.node, R.dist + 1)\n",
    "            return Result(node, L.dist + 1)\n",
    "\n",
    "        return dfs(root).node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            return root\n",
    "\n",
    "\n",
    "        max_depth = 0\n",
    "        queue = [[root]]\n",
    "\n",
    "        leafs = []\n",
    "        \n",
    "        while queue:\n",
    "            nodes = queue.pop()\n",
    "            print(\"len(nodes):\", len(nodes))\n",
    "            if max_depth < len(nodes):\n",
    "                max_depth = len(nodes)\n",
    "\n",
    "            if not nodes[-1].left and not nodes[-1].right:\n",
    "                leafs.append(nodes)\n",
    "            elif nodes[-1].left and nodes[-1].right:\n",
    "                new_nodes = copy.copy(nodes)\n",
    "                new_nodes.append(nodes[-1].left)\n",
    "                nodes.append(nodes[-1].right)\n",
    "                queue.append(new_nodes)\n",
    "                queue.append(nodes)\n",
    "            elif nodes[-1].left:\n",
    "                nodes.append(nodes[-1].left)\n",
    "                queue.append(nodes)\n",
    "            else:\n",
    "                nodes.append(nodes[-1].right)\n",
    "                queue.append(nodes)\n",
    "\n",
    "\n",
    "        l = []\n",
    "        for nodes in leafs:\n",
    "            if len(nodes) == max_depth:\n",
    "                l.append(nodes)\n",
    "        print(\"leafs count:\", len(leafs))\n",
    "        print(\"max_depth:\", max_depth)\n",
    "\n",
    "        for i in range(max_depth-1, -1, -1):\n",
    "            all_equal = True\n",
    "            for pos in range(len(l)-1):\n",
    "                if l[pos][i] != l[pos+1][i]:\n",
    "                    all_equal = False\n",
    "                    break\n",
    "            if all_equal:\n",
    "                #print(i)\n",
    "                #print(l)\n",
    "                return l[0][i]\n",
    "\n",
    "\n",
    "                \n",
    "            \n",
    "\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        nodes = []\n",
    "        queue = [(root, 0)]\n",
    "        while queue:\n",
    "            nq = []\n",
    "            d = SortedDict()\n",
    "            for node, idx in queue:\n",
    "                d[idx] = node\n",
    "                if node.left:\n",
    "                    nq.append((node.left, 2*idx))\n",
    "                if node.right:\n",
    "                    nq.append((node.right, 2*idx+1))\n",
    "            queue = nq\n",
    "            nodes.append(d)\n",
    "        res = list(nodes[-1].keys())\n",
    "        if len(res) == 1:\n",
    "            return nodes[-1][res[0]]\n",
    "        \n",
    "        depth = len(nodes) - 1\n",
    "        while len(res) > 1:\n",
    "            n_res = set()\n",
    "            for val in res:\n",
    "                n_res.add(val // 2)\n",
    "            depth -= 1\n",
    "            res = n_res\n",
    "        return nodes[depth][list(res)[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, None\n",
    "            hl, lca1 = dfs(node.left)\n",
    "            hr, lca2 = dfs(node.right)\n",
    "            if hl > hr:\n",
    "                return hl + 1, lca1\n",
    "            if hl < hr:\n",
    "                return hr + 1, lca2\n",
    "            return hl + 1, node\n",
    "        return dfs(root)[1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        maxDepth = 0\n",
    "        ans = root\n",
    "        def dfs(root, depth):\n",
    "            nonlocal maxDepth, ans\n",
    "            if not root:\n",
    "                maxDepth = max(maxDepth, depth)\n",
    "                return depth\n",
    "            left = dfs(root.left, depth+1)\n",
    "            right = dfs(root.right, depth+1)\n",
    "            if left == right == maxDepth:\n",
    "                ans = root\n",
    "            return max(left, right)\n",
    "\n",
    "        dfs(root, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def f(node):\n",
    "            if node is None:\n",
    "                return 0, None\n",
    "            \n",
    "            l_d, left = f(node.left)\n",
    "            r_d, right = f(node.right)\n",
    "\n",
    "            if l_d > r_d:\n",
    "                return l_d + 1, left\n",
    "            if l_d < r_d:\n",
    "                return r_d + 1, right\n",
    "            \n",
    "            return l_d + 1, node \n",
    "        \n",
    "        return f(root)[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
